#ifndef STX_ALGORITHM_FIND_END_HPP
#define STX_ALGORITHM_FIND_END_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class BinaryPredicate, class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1
find_end_impl(
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    ForwardIterator2 last2,
    BinaryPredicate pred,
    std::forward_iterator_tag,
    std::forward_iterator_tag)
{
    ForwardIterator1 r = last1;  // default return value
    if (first2 == last2) {
        return r;
    }
    while (1) {
        while (1) {
            if (first1 == last1) {       // if source exhausted return last correct answer
                return r;                //    (or last1 if never found)
            }
            if (pred(*first1, *first2)) {
                break;
            }
            ++first1;
        }
        // *first1 matches *first2, now match elements after here
        ForwardIterator1 m1 = first1;
        ForwardIterator2 m2 = first2;
        while (1) {
            if (++m2 == last2) {   // Pattern exhaused, record answer and search for another one
                r = first1;
                ++first1;
                break;
            }
            if (++m1 == last1) {   // Source exhausted, return last answer
                return r;
            }
            if (!pred(*m1, *m2)) { // mismatch, restart with a new first
                ++first1;
                break;
            }  // else there is a match, check next elements
        }
    }
}

template <class BinaryPredicate, class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator1
find_end_impl(
    BidirectionalIterator1 first1,
    BidirectionalIterator1 last1,
    BidirectionalIterator2 first2,
    BidirectionalIterator2 last2,
    BinaryPredicate pred,
    std::bidirectional_iterator_tag,
    std::bidirectional_iterator_tag)
{
    if (first2 == last2) {
        return last1;  // Everything matches an empty sequence
    }
    BidirectionalIterator1 l1 = last1;
    BidirectionalIterator2 l2 = last2;
    --l2;
    while (1) {
        // Find last element in sequence 1 that matchs *(last2-1), with a mininum of loop checks
        while (1) {
            if (first1 == l1) { // return last1 if no element matches *first2
                return last1;
            }
            if (pred(*--l1, *l2)) {
                break;
            }
        }
        // *l1 matches *l2, now match elements before here
        BidirectionalIterator1 m1 = l1;
        BidirectionalIterator2 m2 = l2;
        while (1) {
            if (m2 == first2) { // If pattern exhausted, m1 is the answer (works for 1 element pattern)
                return m1;
            }
            if (m1 == first1) { // Otherwise if source exhaused, pattern not found
                return last1;
            }
            if (!pred(*--m1, *--m2)) { // if there is a mismatch, restart with a new l1
                break;
            }  // else there is a match, check next elements
        }
    }
}

template <class BinaryPredicate, class RandomAccessIterator1, class RandomAccessIterator2>
inline RandomAccessIterator1
find_end_impl(
    RandomAccessIterator1 first1,
    RandomAccessIterator1 last1,
    RandomAccessIterator2 first2,
    RandomAccessIterator2 last2,
    BinaryPredicate pred,
    std::random_access_iterator_tag,
    std::random_access_iterator_tag)
{
    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
    typename std::iterator_traits<RandomAccessIterator2>::difference_type len2 = last2 - first2;
    if (len2 == 0) {
        return last1;
    }
    typename std::iterator_traits<RandomAccessIterator1>::difference_type len1 = last1 - first1;
    if (len1 < len2) {
        return last1;
    }
    const RandomAccessIterator1 s = first1 + (len2 - 1); // End of pattern match can't go before here
    RandomAccessIterator1 l1 = last1;
    RandomAccessIterator2 l2 = last2;
    --l2;
    while (1) {
        while (1) {
            if (s == l1) {
                return last1;
            }
            if (pred(*--l1, *l2)) {
                break;
            }
        }
        RandomAccessIterator1 m1 = l1;
        RandomAccessIterator2 m2 = l2;
        while (1) {
            if (m2 == first2) {
                return m1;
            } // no need to check range on m1 because s guarantees we have enough source
            if (!pred(*--m1, *--m2)) {
                break;
            }
        }
    }
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
inline ForwardIterator1
find_end(
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    ForwardIterator2 last2,
    BinaryPredicate pred)
{
    return stx::find_end_impl<typename add_lvalue_reference<BinaryPredicate>::type>(
        first1,
        last1,
        first2,
        last2,
        pred,
        typename std::iterator_traits<ForwardIterator1>::iterator_category(),
        typename std::iterator_traits<ForwardIterator2>::iterator_category());
}

template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1
find_end(
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    ForwardIterator2 last2)
{
    typedef typename std::iterator_traits<ForwardIterator1>::value_type v1;
    typedef typename std::iterator_traits<ForwardIterator2>::value_type v2;
    return stx::find_end(first1, last1, first2, last2, equal_to<v1, v2>());
}

} // namespace stx

#endif // STX_ALGORITHM_FIND_END_HPP
